package priorityQueue;

import java.util.Arrays;

public class MyPriorityQueue {
	//对于节点i，其父节点的位置为: (i-1)/2
	//             左孩子的位置为: 2*i+1 ;  右孩子的位置为: 2*i+2
	//size: 表示当前有效的数据，如果一个节点的位置 i>size => 表示位置不存在,非法位置
	public int[] elem;
    public int size;     //实际大小

    private void swap(int[] arr,int i,int j) {
    	int tmp=arr[i];
    	arr[i]=arr[j];
    	arr[j]=tmp;	
    }
    public MyPriorityQueue() {
    	elem=new int[11];
    }

    //建堆的时间复杂度：O(n),尤其注意!!!
    public void createHeap(int[] array) {
    	
    	for(int i=0;i<array.length;i++) {
    		elem[i]=array[i];
    		size++;
    	}
    	for(int i=(size-1-1)/2;i>=0;i--) {
    		shiftDown(i, size);
    	}
    }

    //i为要调整的位置
    //size为数组实际大小
    //向下调整的时间复杂度：O(logn)
    private void shiftDown(int i,int size) {
    	int child=2*i+1;
    	while(child<size) {  //只有节点有孩子就进循环
    		//获取孩子节点最大值所在下标
    		//1.如果无右孩子=》index=child   
    		//2.有左右孩子  =》index=elem[child]<elem[child+1]?child+1:child
    		int maxPos=(child+1<size)&&(elem[child]<=elem[child+1])?child+1:child;
    		//如果已经是大根堆，则无需调整
    		if(elem[maxPos]<=elem[i]) {
    			break;
    		}
    		//节点交换，位置更新
    		swap(elem,i,maxPos);
    		i=maxPos;
    		child=2*i+1;
    	}
    }

    //向上调整算法: 只要不满足条件，就交换元素，一直向上，直到满足条件
    private void shiftUp(int i) {
    	int parent=(i-1)/2;
    	while(parent>=0) {
    		if(elem[i]>elem[parent]) {  //如果i节点>父节点，交换，直到满足条件
    			swap(elem,i,parent);
    			i=parent;
    			parent=(i-1)/2;
    		}
    		else {
    			break;
    		}
    	}
    }
    //入队：仍然要保持是大根堆
    public void push(int val) {
    	if(isFull()) {
    		elem=Arrays.copyOf(elem,2*elem.length);
    	}
    	elem[size]=val;
    	//插入完向上调整到适合位置
    	shiftUp(size);
    	size++;
    }

    

    public boolean isFull() {
    	return size==elem.length;
    }

    //出队【删除】：每次删除的都是优先级高的元素
    //仍然要保持是大根堆
    public int pollHeap() {
    	if(isEmpty()) {
    		return -1;
    	}
    	int ret=elem[0];
    	swap(elem,0,size-1);
    	size--;
    	shiftDown(0,size);
    	return ret;
    }

    public boolean isEmpty() {
    	return size==0?true:false;
    }

    //获取堆顶元素
    public int peekHeap() {
    	if(isEmpty()) {
    		return -1;
    	}
    	return elem[0];
    }
    public void display() {
    	for(int i=0;i<size;i++) {
    		System.out.print(elem[i]+" ");
    	}
    	System.out.print("\n");
    }
    public static void main(String[] args) {
    	int[] array=new int[] {21,13,7,9,3,17,27,20,1,6,25};
		MyPriorityQueue priorityQueue=new MyPriorityQueue();
		priorityQueue.createHeap(array);
		priorityQueue.display();
		System.out.println("=============================================");
		priorityQueue.pollHeap();
		priorityQueue.pollHeap();
		priorityQueue.display();
		System.out.println("=============================================");
		priorityQueue.push(2);
		priorityQueue.push(5);
		priorityQueue.push(8);
		priorityQueue.display();
		System.out.println("=============================================");
	}
}
